package com.south.base.test.arithmetic.arrays;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2020/7/1 9:49
 */
public class CompareTwoArr {
    /**
     * 最长重复子数组
     * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
     */
    @Test
    public void findLength() {
        Assert.assertEquals(3, findLength(new int[]{1, 2, 3, 2, 1}, new int[]{3, 2, 1, 4, 7}));
    }

    public int findLength(int[] A, int[] B) {
        return A.length < B.length ? findMax(A, B) : findMax(B, A);
    }

    private int findMax(int[] a, int[] b) {
        int max = 0;
        int lenA = a.length, lenB = b.length;
        for (int len = 1; len <= lenA; len++) {
            max = Math.max(max, maxLen(a, 0, b, lenB - len, len));
        }
        for (int j = lenB - lenA; j >= 0; j--) {
            max = Math.max(max, maxLen(a, 0, b, j, lenA));
        }
        for (int i = 1; i < lenA; i++) {
            max = Math.max(max, maxLen(a, i, b, 0, lenA - i));
        }
        return max;
    }

    private int maxLen(int[] a, int indexA, int[] b, int indexB, int len) {
        int count = 0, max = 0;
        for (int k = 0; k < len; k++) {
            if (a[indexA + k] == b[indexB + k]) {
                count++;
            } else if (count > 0) {
                max = Math.max(max, count);
                count = 0;
            }
        }
        return count > 0 ? Math.max(max, count) : max;
    }
}
